/**
 * Se da un labirint sub forma de matrice cu m linii si n coloane.
 * Fiecare element al matricei reprezinta o camera a labirintului.
 * Într-una din camere, de coordonate x si y, se gaseste un om.
 * Se cere sa se gaseasca toate iesirile din labirint.
 *
 */

#include <stdlib.h>
#include <stdio.h>
#include <conio.h>

#define in_filename ("labirint.txt")

#define trap     ('*')
#define space    (' ')
#define me(x)    ((x)==trap||(x)=='x'||(x)=='X')
#define empty(x) ((x)==space||(x)=='0'||me(x))

#define _N     30
#define _UP    1
#define _RIGHT 2
#define _DOWN  4
#define _LEFT  8

typedef char tCell;
typedef tCell tRow[_N];
typedef tRow  tMap[_N];
typedef unsigned tSize;
typedef tSize tSol[100][2];

tMap map, dmap;
tSol sol;
tSize m,n;
int x,y; 


int  read_lab(char *fn);
void print_lab(tMap map);
int  ies(int x, int y, int k);

int main()
{
    clrscr();

    if(!read_lab(in_filename)) {
       printf("Nu exista fisierul %s!\n", in_filename);
       return 1;
    }
    printf("\nHarta (%dx%d):\n", n, m);
    print_lab(map);
    
    while(x < 0 || y < 0) {
       printf("\nPozitia (x, y):");
       scanf("%d %d", &x, &y);
       x--; y--;
       if(!empty(map[y][x]) || x >= n || y >= m) {
          printf("Perete!");
          x = -1;
       }
    }

    printf("\nHarta directiilor codificate hex:\n");
    print_lab(dmap);
    
    getch();
    printf("\nSolutii:\n");

    if(!ies(x,y,0)) {
       printf("\nNu sunt solutii :-(\n");
       getch();
    }
    
    return 0;
}

char tonr(tCell c) {
   if( 0 <= c && c <=  9) return c + '0';
   if(10 <= c && c <= 15) return c + 'A' - 10;
   return c;
}

void print_lab(tMap map) {
   tSize i,j;
   
   for(i = 0; i < m; i++) {
      for(j = 0; j < n; j++) printf("%c", tonr(map[i][j]));
      printf("\n");
   }
}

void tipar(int k) {
    int i;
    printf("--------------\n");
    for(i=0; i<k; i++) printf("(x,y)=(%d,%d)\n", sol[i][0]+1, sol[i][1]+1);
    getch(); 
}

void print_sol(int k)
{
   tSize i,j;
   for(i = 0; i < m; i++) for(j = 0; j < n; j++) if(empty(map[i][j])) map[i][j] = space;
   for(i = 0; i < k; i++) map[sol[i][1]][sol[i][0]] = trap;
   print_lab(map);
   getch(); 
}

int ies(int x, int y, int k)
{
    tCell c = dmap[y][x];
    int i, r = 1;

    if(!c) return 0; // Inkis

    sol[k][0] = x;
    sol[k][1] = y;
    
    if(x == 0 || x == n-1 || y == 0 || y == m-1) print_sol(k); // se poate tipar(k); // Am ajuns la margine
    else {
        for(i=0; i<k; i++) if(sol[i][0]==sol[k][0] && sol[i][1]==sol[k][1]) { r = 0; break; }
        if(r) {
            r = 0; // Presupunem ca nu sunt solutii
            k++;
            if( _LEFT  & c )  r |= ies(x-1,y  ,k);
            if( _RIGHT & c )  r |= ies(x+1,y  ,k);
            if( _UP    & c )  r |= ies(x  ,y-1,k);
            if( _DOWN  & c )  r |= ies(x  ,y+1,k);
        }
    }
    return r; // 0 - nu sunt solutii, 1 - sunt solutii
}

void norm_lab() {
   tSize i,j;
   tCell d = 0, a = 0;
   for(i = 0; i < m; i++) {
      a = 0;
      for(j = 0; j < n; j++) {
         if(a) map[i][j] = a; else if(!map[i][j]) a = '#'; // Completam liniile incomplete
         if(!empty(map[i][j])) d = 0;
         else {
           if( j == 0   || empty(map[i][j-1]) ) d |= _LEFT;
           if( j == n-1 || empty(map[i][j+1]) ) d |= _RIGHT;
           if( i == 0   || empty(map[i-1][j]) ) d |= _UP;
           if( i == m-1 || empty(map[i+1][j]) ) d |= _DOWN;
         }
         dmap[i][j] = d;
      }
   }
}

int read_lab(char *fn) {
   FILE* f;
   tRow  r;
   tSize i = 0;
   
   if(f = fopen(fn, "r")) {
       m = n = 0;
       x = y = -1;
       while(fgets(r, _N, f)) {
           i = 0;
           while(r[i] && r[i] != '\n' && r[i] != '\r') {
              if(me(r[i])) {
                 x = i;
                 y = m;
              }
              map[m][i] = r[i];
              i++;
           }
           map[m][i] = 0;
           if(i>n) n = i;
           m++;
           map[m][0] = 0;
       }
       fclose(f);
       norm_lab();
       return 1;
   } else return 0;
}